package com.atwulidun.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//public class BinarySearch {
//    public static void main(String[] args) {
//        int[] arr = {1,2,3,4,5,5,5,6,6,7,8};
//        ArrayList<Integer> list = binarySearch(arr, 0, arr.length - 1, 9);
//        System.out.println(list);
//    }
//
//    public static ArrayList<Integer> binarySearch(int[] arr, int left, int right, int findVal) {
//        // 递归结束条件一：找不到就返回一个空的ArrayList<Integer>
//        if (left > right) {
//            return new ArrayList<>();
//        }
//        // 求出中间数的坐标并找出中间数
//        int mid = left + (right - left) / 2;
//        int midVal = arr[mid];
//
//        // 对findVal和midVal进行比较，分为三种情况：
//        if (findVal < midVal) {
//            // 左递归
//            return binarySearch(arr, left, mid - 1, findVal);// 特别注意这里的右边界是mid - 1而不是mid，不包括中间数！！！！！！！
//        } else if (findVal > midVal) {
//            // 右递归
//            return binarySearch(arr, mid + 1, right, findVal);
//        } else {
//            // 这种情况是中间数刚好就是要找的数
//            // 因为进行二分查找的数组是有序的，因此相同的数是连在一起的，所以找到后再扫描两边有没有相同的数
//            // 1.先创建一个ArrayList<Integer>来保存找到的数的坐标
//            ArrayList<Integer> list = new ArrayList<>();
//            // 2.向左边扫描
//            // 创建一个扫描指针，从中间数的左边第一个开始
//            int leftIndex = mid - 1;
//            // 遇到相同的数就加到list中
//            while (leftIndex >= 0 && arr[leftIndex] == findVal) {
//                list.add(leftIndex);
//                leftIndex--;
//            }
//            // 3.将mid添加到list中
//            list.add(mid);
//            // 4.向右扫描
//            // 创建一个扫描指针，从中间数的右边第一个开始
//            int rightIndex = mid + 1;
//            while (rightIndex <= arr.length - 1 && arr[rightIndex] == findVal) {
//                list.add(rightIndex);
//                rightIndex++;
//            }
//            // 5.全部加完后将list返回即可
//            return list;
//        }
//    }
//}

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,5,5,6,6,7,8};
        List<Integer> list = iterativeBinarySort(arr, 0, arr.length - 1, 5);
        System.out.println(list);
    }


    private static List<Integer> recursiveBinarySort(int[] arr, int left, int right, int findVal) {
        if (left > right) {
            return new ArrayList<>();
        }
        int mid = left + (right - left) / 2;
        if (findVal < arr[mid]) {
            return recursiveBinarySort(arr, left, right - 1, findVal);
        } else if (findVal > arr[mid]) {
            return recursiveBinarySort(arr, left + 1, right, findVal);
        } else {
            List<Integer> list = new ArrayList<>();
            int leftIndex = mid - 1;
            while (leftIndex >= 0 && arr[leftIndex] == findVal) {
                list.add(leftIndex--);
            }
            list.add(mid);
            int rightIndex = mid + 1;
            while (rightIndex <= arr.length - 1 && arr[rightIndex] == findVal) {
                list.add(rightIndex++);
            }
            return list;
        }
    }

    private static List<Integer> iterativeBinarySort(int[] arr, int left, int right, int findVal) {
        List<Integer> list = new ArrayList<>();
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (findVal < arr[mid]) {
                right = mid - 1;
            } else if (findVal > arr[mid]) {
                left = mid + 1;
            } else {
                int leftIndex = mid - 1;
                while (leftIndex >= 0 && arr[leftIndex] == findVal) {
                    list.add(leftIndex--);
                }
                list.add(mid);
                int rightIndex = mid + 1;
                while (rightIndex <= arr.length - 1 && arr[rightIndex] == findVal) {
                    list.add(rightIndex++);
                }
                return list;
            }
        }
        return list;
    }
}